#include"include.h"

dict_node_t *newdictnode()
{
   dict_node_t *nnode = malloc(sizeof(dict_node_t));
   nnode->left = nnode->right = nnode->key = nnode->val = NULL;
   return nnode;
}

dict_t *newDict(int (*compare)(const void *, const void *))
{
   dict_t *ndict = malloc(sizeof(dict_t));
   ndict->root = NULL;
   ndict->compare = compare;
   ndict->size = 0;
   sem_init(&ndict->lock, 0, 1);
   return ndict;
}

void sdictClear(dict_node_t **n)
{
   if ((*n)->left != NULL)
      sdictClear(&((*n)->left));
   if ((*n)->right != NULL)
      sdictClear(&((*n)->right));
   free(*n);
   *n = NULL;
}

void dictClear(dict_t *dict)
{
   if(dict == NULL)
      return;
   else if(dict->root != NULL)
      sdictClear(&(dict->root));
   dict->size = 0;
}

void sdictClearKeysVals(dict_node_t **n)
{
   if ((*n)->left != NULL)
      sdictClear(&((*n)->left));
   if ((*n)->right != NULL)
      sdictClear(&((*n)->right));
   free((*n)->key);
   free((*n)->val);
   free(*n);
   *n = NULL;
}

void dictClearKeysVals(dict_t *dict)
{
   if(dict == NULL)
      return;
   else if(dict->root != NULL)
      sdictClearKeysVals(&(dict->root));
   dict->size = 0;
}

void *sdictPut(dict_node_t **n, const void *key, const void *val, 
   int (*compare)(const void *, const void*))
{
   void *ret = NULL;
   if (*n == NULL)
   {
      *n = newdictnode();
      (*n)->key = (void *) key;
      (*n)->val = (void *) val;
   }
   else
   {
      int c = compare(key, (*n)->key);
      if (c < 0)
         ret = sdictPut(&((*n)->left), key, val, compare);
      else if (c > 0)
         ret = sdictPut(&((*n)->right), key, val, compare);
      else
      {
         ret = (*n)->val;
         (*n)->val = (void *) val;
      }
   }
   return ret;
}

void *dictPut(dict_t *dict, const void *key, const void *val)
{
   void *ret = sdictPut(&(dict->root), key, val, dict->compare);
   if(ret != NULL)
      dict->size++;
   return ret;
}

void *sdictGet(dict_node_t *n, void *key,
   int (*compare) (const void *, const void *))
{
   void *ret;
   if (n == NULL)
      ret = NULL;
   else
   {
      int c = compare(key, n->key);
      if (c < 0)
         ret = sdictGet(n->left, key, compare);
      else if (c > 0)
         ret = sdictGet(n->right, key, compare);
      else
         ret = n->val;
   }
   return ret;
}

void *dictGet(dict_t *dict, void *key)
{
   return sdictGet(dict->root, key, dict->compare);
}

int  dictIsEmpty(dict_t *dict)
{
   return dict->root == NULL;
}

dict_node_t **sfindNode(dict_node_t **r, void *key,
   int (*compare) (const void *, const void *))
{
   dict_node_t **ret = NULL;
   if (r != NULL && *r != NULL)
   {
      int c = compare(key, (*r)->key);
      if(c < 0)
         ret = sfindNode(&((*r)->left), key, compare);
      else if (c > 0)
         ret = sfindNode(&((*r)->right), key, compare);
      else
         ret = r;
   }
   return ret;
}

int sdictRemove(dict_node_t **n, void *key,
   int (*compare) (const void *, const void *))
{
   dict_node_t **f;
   if((f = sfindNode(n, key, compare)) == NULL)
      return 0;
   int l = (*f)->left == NULL;
   int r = (*f)->right == NULL;

   // Delete f
   // Leaf case
   if(l && r)
   {
      free(*f);
      *f = NULL;
   } // Right child
   else if(l)
   {
      dict_node_t *fill = (*f)->right;
      free(*f);
      *f = fill;
   } // Left child
   else if(r)
   {
      dict_node_t *fill = (*f)->left;
      free(*f);
      *f = fill;
   } // Double child
   else
   {  // Get leftmost child of right child
      dict_node_t **fill = &((*f)->right);
      while((*fill)->left != NULL)
         fill = &((*fill)->left);
      // Swap the info in the node to delete and fill
      (*f)->key = (*fill)->key;
      (*f)->val = (*fill)->val;
      // Delete fill instead
      free(*fill);
      *fill = NULL;
   }
   return 1;
}

void dictRemove(dict_t *dict, void *key)
{
   if (dict == NULL || dict->root == NULL)
      return;
   if(sdictRemove(&(dict->root), key, dict->compare))
      dict->size--;
}

int  dictContainsKey(dict_t *dict, void *key)
{
   dict_node_t **f = sfindNode(&(dict->root), key, dict->compare);
   return f != NULL;
}

int  dictSize(dict_t *dict)
{
   return dict->size;
}

void dictLock(dict_t *dict)
{
   sem_wait(&(dict->lock));
}

void dictRelease(dict_t *dict)
{
   sem_post(&(dict->lock));
}

void dictTraversalHelper(list_t *l, dict_t *dict, dict_node_t *n)
{
   if(n == NULL)
      return;
   dictTraversalHelper(l, dict, n->left);
   dict_key_val_t *kv = malloc(sizeof(dict_key_val_t));
   kv->key = n->key;
   kv->val = n->val;
#ifdef DEBUG
   printf("Traversing %s\n", (char *)kv->key);
#endif
   addObject(l, kv);
   dictTraversalHelper(l, dict, n->right);
}


list_t *dictTraversal(dict_t *dict)
{
#ifdef DEBUG
   printf("\nTraversing dict\n");
#endif

   list_t *l = createList();
   dictTraversalHelper(l, dict, dict->root);

#ifdef DEBUG
   printf("Traversal done\n\n");
#endif
   return l;
}

int integerCompare(const unsigned int *x, const unsigned int *y)
{
   return (*x > *y) ? 1 : *x == *y ? 0 : -1;
}
